Theory of Computation
Q71.
Let G = ({S}, {a, b} R, S) be a context free grammar where the rule set R is S\rightarrow aSb|SS|\epsilon Which of the following statements is true?Q72.
Consider the grammar shown below. S \rightarrow C C C \rightarrow cC | d The grammar isQ73.
Consider the following decision problems: (P1): Does a given finite state machine accept a given string? (P2): Does a given context free grammar generate an infinite number of strings? Which of the following statements is true?Q74.
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: If G is a context free grammar and w is a string of length l in L(G), how long is a derivation of w in G, if G is in Chomsky normal form?Q75.
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: For a context free grammar, FOLLOW(A) is the set of terminals that can appear immediately to the right of non-terminal A in some "sentential" form. We define two sets LFOLLOW(A) and RFOLLOW(A) by replacing the word "sentential" by "left sentential" and "right most sentential" respectively in the definition of FOLLOW (A).Q77.
Consider a grammar with the following productions S \rightarrow a \alpha b \mid b \alpha c \mid aB S \rightarrow \alpha S\mid b S \rightarrow \alpha b b\mid ab S \alpha \rightarrow bd b\mid b The above grammar is:Q78.
Choose the correct alternatives (more than one may be correct ) and write the corresponding letters only: Consider the SLR(1) and LALR (1) parsing tables for a context free grammar. Which of the following statement is/are true?Q80.
Define a context free languages L \in \{0, 1\}^*, \text{init} (L) = \{u \mid uv \in L for some v in \{0, 1\}^*\} ( in other words, \text{init}(L) is the set of prefixes of L) Let L = \{w \mid w \text{ is nonempty and has an equal number of $0$'s and $1$'s}\} Then \text{init}(L) is: